package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-ii/'>二叉树的最近公共祖先 II(Lowest Common Ancestor of a Binary Tree II)</a>
 * <p>给定一棵二叉树的根节点 root，返回给定节点 p 和 q 的最近公共祖先（LCA）节点。如果 p 或 q 之一 不存在 于该二叉树中，返回 null。树中的每个节点值都是互不相同的。</p>
 * <p><a href='https://en.wikipedia.org/wiki/Lowest_common_ancestor'>最近公共祖先节点的定义</a>：“两个节点 p 和 q 在二叉树 T 中的最近公共祖先节点是 后代节点 中既包括 p 又包括 q 的最深节点（我们允许 一个节点为自身的一个后代节点 ）”。一个节点 x 的 后代节点 是节点 x 到某一叶节点间的路径中的节点 y。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 *                           3
 *                        /    \
 *                       5      1
 *                      / \    / \
 *                     6   2  0   8
 *                        / \
 *                       7   4
 *      输出： 3
 *      解释： 节点 5 和 1 的共同祖先节点是 3。
 *
 * 示例 2:
 *      输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 *                           3
 *                        /    \
 *                       5      1
 *                      / \    / \
 *                     6   2  0   8
 *                        / \
 *                       7   4
 *      输出： 5
 *      解释： 节点 5 和 4 的共同祖先节点是 5。根据共同祖先节点的定义，一个节点可以是自身的后代节点。
 *
 * 示例 3:
 *      输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10
 *      输出： null
 *      解释： 节点 10 不存在于树中，所以返回 null。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>树中节点个数的范围是 [1, 10^4]</li>
 *     <li>-10^9 <= Node.val <= 10^9</li>
 *     <li>所有节点的值 Node.val 互不相同</li>
 *     <li>p != q</li>
 * </ul>
 * </p>
 * <p>
 * 进阶： 在不检查节点是否存在的情况下，你可以遍历树找出最近公共祖先节点吗？
 *
 * @author c2b
 * @see LC0235LowestCommonAncestorOfABinarySearchTree_M 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree)
 * @see LC0236LowestCommonAncestorOfABinaryTree_M 二叉树的最近公共祖先(Lowest Common Ancestor of a Binary Tree)
 * @see LC1644LowestCommonAncestorOfBinaryTree_II_M 二叉树的最近公共祖先 II(Lowest Common Ancestor of a Binary Tree II)
 * @see LC1650LowestCommonAncestorOfBinaryTree_III_M 二叉树的最近公共祖先 III(Lowest Common Ancestor of a Binary Tree III)
 * @since 2023/12/5 10:55
 */
public class LC1644LowestCommonAncestorOfBinaryTree_II_M {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        // 在左子树上找最近公共祖先
        TreeNode leftLowestCommonAncestor = lowestCommonAncestor(root.left, p, q);
        // 在右子树上找最近公共祖先
        TreeNode rightLowestCommonAncestor = lowestCommonAncestor(root.right, p, q);
        // 如果都找到了，说明公共祖先为root
        if (leftLowestCommonAncestor != null && rightLowestCommonAncestor != null) {
            return root;
        }
        // 如果在左子树中找到了，说明公共祖先为 leftLowestCommonAncestor
        if (leftLowestCommonAncestor != null) {
            return leftLowestCommonAncestor;
        }
        if (rightLowestCommonAncestor != null) {
            return rightLowestCommonAncestor;
        }
        // 如果在右子树中找到了，说明公共祖先为 rightLowestCommonAncestor；否则为 null
        return null;
    }
}
